// 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

#include<bits/stdc++.h>
using namespace std;

// 递归O(n)
// 执行用时：
// 4 ms
// , 在所有 C++ 提交中击败了
// 91.12%
// 的用户
// 内存消耗：
// 8.3 MB
// , 在所有 C++ 提交中击败了
// 13.63%
// 的用户

struct ListNode {
     int val;
    ListNode *next;
   ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 空链表
        if(head==nullptr){
            return head;
        }
        // 单节点
        if(head->next==nullptr){
            return head;
        }
        // 递归返回的是结果链表head
        ListNode* new_head = reverseList(head->next);
        // 一直递归到最后一个节点，head->next==nullptr
        // 此时new_head为最后一个节点地址，应该作为结果链head
        // 所以，调用该此节点的前节点应该作为结果链的的下一节点
        // new_head->next = head
        // 但是不能用new_head->next,因为是固定的地址，应该使用head->next->next
        // 上一递归由于head->next还在原链表且与结果链最后节点地址相同，可以再次连接
        head->next->next = head;

        // 因为head已经加入new_head,断开，否则new_head->next还连接着new_head，成环
        head->next = nullptr;
        return new_head;
    }

};